(1) Field of the Invention
The present invention relates to an interleaving method and a de-interleaving method, an interleaving apparatus and a de-interleaving apparatus, an interleaving/de-interleaving system, and an interleaving/de-interleaving apparatus, which can suitably rearrange a data array.
(2) Description of Related Art
In radio communications, there is a case where data transmitted from a transmitter to a receiver is affected by fading during transmission so that the data is changed to erroneous data differing from received contents.
As a technique dealing with fading, there are interleaving and de-interleaving. Interleaving is a technique of rearranging an order of data to be transmitted, and outputting the data when the data is transmitted from a transmitter, for example. On the other hand, de-interleaving is a technique of rearranging an order of the interleaved data transmitted from the transmitter back to an order before interleaved.
Interleaving is classified into block-interleaving and random-interleaving.
Block interleaving is to regularly rearrange an array of data.
For example, data before block-interleaved are “D0, D1, D2, D3, . . . and D383”. Incidentally, the data will be described as “0, 1, 2, 3, . . . and 383”, hereinafter.
These 384 (0-383) of data are assumed to be, as shown in FIG. 22, arranged in a matrix of 24 rows by 16 columns in a storing unit. When written, the data is rearranged in order in the direction of rows, and read out from each column (A′-P′) in order.
The data read out is rearranged into “000”, “016”, “032”, “048”, “064”, “080”, “096”, “112”, “128”, “144”, “160”, “176”, . . . “351”, “367”, and “383”. In a sequence of interleaved data, data numbers having been spaced at mostly 15 of data are arranged such as “000”, “016”, “031” and so on.
When reading of the last data “368” in the column A′ is completed in reading the data, the leading data “001” in column B′ is next read out. At the ending/beginning of other column, the data is read out in the similar manner. When the last data “383” is read out, the leading data in column A′ is next read out.
On the other hand, when the receiver receives block-interleaved data, the receiver rearranges the data in the order of the data before interleaved by performing the reverse processing.
The block-interleaved data is affected by fading during transmission while transmitted from the transmitter to the receiver, changed into contents different from the transmitted contents, and received with burst errors by the receiver. Assuming that burst errors generate in the data in column B′ (001, 017, 033, 049, 065, 081, 097, 113, 129, 145, 161, 177, 193, 209, 225, 241, 257, 273, 289, 305, 321, 337, 353 and 369) shown in FIG. 22, for example.
The receiver de-interleaves the received data to rearrange the data in the order before interleaved in the transmitter (000, 001, 002, 003, 004, . . . 381, 382 and 383).
The erroneous data continuously generated in the transmitted data is thereby regularly distributed. Namely, the erroneous data is spaced at every 15 data numbers so as to be distributed and arranged in the data (000-383).
The erroneous data is corrected by an error correcting function in consideration of a relation with the preceding/following data.
Accordingly, block interleaving/block de-interleaving facilitate correction of continuous errors by regularly distributing the errors, as above.
When burst errors generate in the leading data “001” in column B′ to the data “130” in column C′, for example, the erroneous data distributed in the de-interleaved data “0-383” might be continuously placed as “001” and “002”. In such case, it possibly occurs that the errors cannot be corrected by the error correcting function.
On the other hand, random interleaving is to randomly rearrange an array of data.
FIG. 23 is a diagram illustrating random interleaving. As shown in FIG. 23, random interleaving is to rearrange the data by writing the data in the order of described numbers in a storing unit and reading the data in alphabetical order.
In the case where the data is randomly written in the storing unit in random interleaving, the data “0-383” is randomly written in a matrix of 24 rows by 16 columns in the storing unit, as shown in FIG. 24, for example.
If the data is read out in the order arranged in the row when read out from the storing unit, the data read out is rearranged in the order of “000”, “255”, “127”, “063”, “031”, “015”, “263”, “240”, “376”, “251”, “125”, . . . , “123”, “061”, “030” and “271”.
The random-interleaved data are rearranged, not following the rule that the block-interleaved data is spaced at every 15 data numbers, when compared with the block-interleaved data.
When reading of the last data “232” in the first row is completed in reading the data, the leading data “116” in the second row is then read out. The reading of the ending/beginning of the data in other row is performed in the similar manner. When the last data “271” is read out, the leading first row is next read out.
On the other hand, when the receiver receives the random-interleaved data, the data random-interleaved is rearranged in the order of the data before random-interleaved in the reverse processing.
The random-interleaved data is affected by fading during transmission when transmitted from the transmitter to the receiver so as to be changed to contents different from the transmitted contents, and received with burst errors by the receiver. Assuming that burst errors generate in the data in the second row (116, 314, 206, 103, 307, 153, 076, 038, 019, 009, 026, 130, 065, 288, 144 and 328) shown in FIG. 24, for example.
The receiver de-interleaves the received data to rearrange the data in the order before interleaved in the transmitter (000, 001, 002, 003, 004, . . . , 381, 382 and 383).
The erroneous data (116, 314, 206, 103, 307, 153, 076, 038, 019, 009, 260, 130, 065, 288, 144 and 328) having continuously generated in the transmitted data is irregularly distributed in the data (000-383).
The erroneous data is corrected by the error correcting function in consideration with a relation with the preceding/following data.
Next, assume that burst errors are generated in the data (198, 099, 305, 152, 332, 166, 083, 041, 276, 197, 354, 177, 088, 300, 150 and 331) in the 14th row shown in FIG. 24.
The erroneous data is distributed in the data (000-383), but each erroneous data is placed in the neighboring positions to each other when rearranged into the state before random-interleaved.
Namely, “083” and “088”, “150” and “152”, “197” and “198”, “300” and “305”, and “331” and “332” in the erroneous data are distributed in totaling 384 (000-383) of data, but the erroneous data is placed in the neighboring positions to each other, which cannot be possibly corrected by the error correcting function.
In such case, errors having generated in bursts are randomly distributed in random interleaving/random de-interleaving. However, positions of the distributed errors are locally close to each other, which leads to deviation of the distribution.
Next, assuming that 65536 (256×256) of data are arranged in a matrix of 256 rows by 256 columns in the storing unit.
Wheni′=129(i+j) mod 256  (1) j′[P(ξ)·(i+1)]−1 mod 256  (2), the data is written in the order of the i-th row and the j-th column, and read out in the order of the il-th row and the jl-th column.
In the above formulae (1) and (2), ξ=(i+j) mode 8, P(0)=17, P(1)=37, P(2)=19, P(3)=29, P(4)=41, P(5)=23, P(6)=13 and P(7)=7 (i, j, i′, j′=0, 1-8).
The data is written in the storing unit in the order of the i-th row and the j-th column (the 1st column and the 1st row, the 1st row and the 2nd column, . . . , the 1st row and the 256th column, the 2nd row and the 1st column, . . . and the 256th row and the 256th column), and read out in the order of the i′-th row and the j′-th column from the storing unit.
(X mod y) represents a remainder generated when x is divided by y.
However, fabrication of an interleaving apparatus which reads according to the above formulae (1) and (2) is not easy since a manner of random generation is complicated.
Fabrication of a de-interleaving apparatus which de-interleaves the data interleaved in the above manner is also not easy.